#ifndef ILLIB_BASICREDBLACKTREE_H_
#define ILLIB_BASICREDBLACKTREE_H_

#include <stddef.h>

namespace illib {
	namespace BasicRedBlackTree{
		class Tree;
		class Node {
		private:
			Node(const Node &other);
		protected:
			bool color_; /* if color_=0 then the node is black */
			Node * left_;
			Node * right_;
			Node * parent_;
			friend class Tree;
			friend class Iterator;
		public:
			Node();
			~Node();
		};

		class TreeFunctions{
		public:
			virtual ~TreeFunctions(){

			}
			virtual bool greater(Node& left, Node& right) = 0;
			virtual bool lesser(Node& left, Node& right) = 0;
			virtual bool equal(Node& left, Node& right) = 0;
		};

		class Iterator {
		private:
			Iterator(const Iterator &other);
		protected:
			Tree &tree_;
			TreeFunctions &functions_;
			Node* x_;
			Node* lastBest_;
			Node &high_;
			Node &low_;
			Node * current_;
			bool forward_;
			void init();
		public:
			Iterator(Node &low, Node &high, Tree &tree, TreeFunctions &functions, bool forward=true);
			Iterator(Node &node, Tree &tree, TreeFunctions &functions, bool forward=true);
			Iterator(Tree &tree, TreeFunctions &functions, bool forward=true);
			Node * next();
			Node * current();
		};

		class Tree {
		private:
			Tree(const Tree &other);
		protected:
			size_t length_;
			Node root_;
			Node nil_;
			void left(Node &node);
			void right(Node &node);
			void remove_(Node &node);

			void CheckAssumptions();
			friend class Iterator;
		public:
			Tree();
			~Tree();
			size_t length();
			Node * remove(Node &node);
			Node * add(Node &node, TreeFunctions &functions);
			Node * predecessor(Node &node);
			Node * successor(Node &node);


			bool lesser(Node& left, Node& right, TreeFunctions &functions);
			bool greater(Node& left, Node& right, TreeFunctions &functions);
			bool greaterOrEqual(Node& left, Node& right, TreeFunctions &functions);
			bool lesserOrEqual(Node& left, Node& right, TreeFunctions &functions);
			bool equal(Node& left, Node& right, TreeFunctions &functions);

			Node & min(){return nil_;}
			Node & max(){return root_;}
			void clear();
		};
	}
}
#endif /* ILLIB_BASICREDBLACKTREE_H_ */
